<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        let arr = [10, 9, 2, 5, 3, 7, 101, 18, 200]

        // getSequence(arr);
        console.log(lengthOfLIS(arr))

        function lengthOfLIS(nums) {
            const n = nums.length
            if (n <=1 ) return n;
            let result = [nums[0]]
            let len = result.length	// 最大长度
            for (let i = 1; i < n; i++) {
                if (nums[i] > result[len-1]) { //大于末尾的值， 直接近栈
                    result.push(nums[i]) 
                    ++len
                } else {
                    let left = 0, right = len;
                    while(left < right) { // 二分查找序列内第一个大于nums[i]的值
                        const mid = (left + right) >> 1
                        if (result[mid] < nums[i]) {
                            left = mid + 1
                        } else {
                            right = mid
                        }
                    }
                    result[left] = nums[i] // 替换
                }
            }
            return len
        }

        // var lengthOfLIS = function(nums) {
        //     if(nums.length<=0) return 0
        //     let dp = new Array(nums.length).fill(1)
        //     for (let i = 0; i < nums.length; i++) {
        //         for (let j = 0; j < i; j++) {
        //             if (nums[j] < nums[i]) {
        //                 dp[i] = Math.max(dp[i], dp[j] + 1)
        //             }
        //         }
        //     }
        //     return Math.max(...dp)
        // };
    </script>
</body>
</html>